package sword.chapter7Queue;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 在完全二叉树添加节点
 * <p>
 * 广度优先搜索-队列
 * 何时删除 当前节点left right都不为null时
 * 何时插入 当前节点left right都不为null时，删除当前节点，插入cur.left cur.right
 * <p>
 * insert逻辑
 * peek最前节点
 * 判断left right节点，为null时赋值。且右节点赋值完后，需要poll删除当前节点，并插入cur.left cur.right
 *
 * @author K
 * @date 2021-12-05 18:19
 */
class S43CBTInserter {
    private Queue<TreeNode> queue;
    private TreeNode root;

    public S43CBTInserter(TreeNode root) {
        this.root = root;
        queue = new LinkedList<>();
        queue.offer(root);
        while (queue.peek().left != null && queue.peek().right != null) {
            TreeNode node = queue.poll();
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }

    private int insert(int val) {
        TreeNode parent = queue.peek();
        TreeNode node = new TreeNode(val);
        if (parent.left == null) {
            parent.left = node;
        } else if (parent.right == null) {
            parent.right = node;
            queue.poll();
            queue.offer(parent.left);
            queue.offer(parent.right);
        }
        return parent.val;
    }

    public TreeNode get_root() {
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
//        TreeNode node11 = new TreeNode(11);
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;

        S43CBTInserter s43CBTInserter = new S43CBTInserter(root);
        int result = s43CBTInserter.insert(7);
        int result2 = s43CBTInserter.insert(8);
        int result3 = s43CBTInserter.insert(9);
        System.out.println();
    }


}
